﻿//Author:  Andrew Smigaj
//Algorithm retrieved off of wikipedia

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PrototypeGA
{
    class Warshal
    {
        static double[,] shortestDistArray;
        static int[,] pathIndexHolder;
        static int numCities;

        public Warshal(double[,] adjacencyMatrix, int num)
        {
            shortestDistArray = adjacencyMatrix;
            numCities = num;
            pathIndexHolder = new int[num, num];
        }


        public double[,] getShortestDistances()
        {
            return shortestDistArray;
        }

        public void calcShortestDistArray()
        {
            for (int i = 0; i < numCities; i++)
            {
                for (int j = 0; j < numCities; j++)
                {
                    for (int k = 0; k < numCities; k++)
                    {
                        if (j != k)
                        {
                            if ((shortestDistArray[j, i] + shortestDistArray[i, k]) < shortestDistArray[j, k])
                            {
                                shortestDistArray[j, k] = shortestDistArray[j, i] + shortestDistArray[i, k];
                                pathIndexHolder[j, k] = i;
                            }
                        }
                    }
                }
            }
        }

        public String getPath(int a, int b)
        {
            

            if (shortestDistArray[a, b] == Double.MaxValue)
            {
                return " ";
            }
            int intermediate = pathIndexHolder[a, b];
            if (intermediate == 0)
            {
                return " " + b + " ";
            }
            else
            {
                return getPath(a, intermediate) + " " + intermediate + " " + getPath(intermediate, b);
            }
        }


    }
}
